We study the problem of learning Single-Index Models under the $L_2^2$ loss
in the agnostic model. We give an efficient learning algorithm, achieving a
constant factor approximation to the optimal loss, that succeeds under a range
of distributions (including log-concave distributions) and a broad class of
monotone and Lipschitz link functions. This is the first efficient constant
factor approximate agnostic learner, even for Gaussian data and for any
nontrivial class of link functions. Prior work for the case of unknown link
function either works in the realizable setting or does not attain constant
factor approximation. The main technical ingredient enabling our algorithm and
analysis is a novel notion of a local error bound in optimization that we term
alignment sharpness and that may be of broader interest.

在罚函数为 $L_2^2$ 的超验模型中，我们研究了学习单指数模型的问题，并提出了一种高效的学习算法，它在一系列分布和广泛类别的单调和 Lipschitz 链函数下，能够以常数因子逼近最优损失。这是第一个高效的常数因子逼近超验学习器，甚至适用于高斯数据和任何非平凡的链函数类别。我们算法与分析的主要技术要素是优化中的一种新概念，我们称之为对齐锐度，这可能具有更广泛的兴趣。